package com.data_structure_test.queue;

import java.util.*;

public class Solution {

    public static void main(String[] args){
        Solution s = new Solution();
        char[] input = new char[]{'A','A','A','B','B','B'};

        System.out.println(s.leastInterval(input,2));
        //直接算方法
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode res = null;
        ListNode tmp1,tmp2,tmpRes = res;
        while((tmp1 = l1.next )!= null && (tmp2 = l2.next) != null){


            if(tmp1.val < tmp2.val){
                insert(tmp1,res,tmpRes);
                l1 = l1.next;
            }else{
                insert(tmp2,res,tmpRes);
                l2 = l2.next;
            }

        }
        return res;

    }

    private void insert(ListNode tmp,ListNode targetRoot,ListNode tmpTarget){
        if(targetRoot == null){
            tmpTarget = targetRoot = tmp;

        }else{
            tmpTarget.next = tmp;
            tmpTarget = tmpTarget.next;
        }
    }

    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

    public int leastInterval(char[] tasks, int n) {

        int res = 0;
        Map<Character,Integer> map = new HashMap<>();

        for(char c : tasks){
            map.compute(c,(k,v) -> {

                if(v == null){
                    v = 1;
                }else{
                    v += 1;
                }
                return v;

            });
            res ++;
        }



        List<Character> list = new ArrayList<>(map.keySet());
        Collections.sort(list,(c1,c2)->{
            return map.get(c1) - map.get(c2);
        });



        int tmp = map.size();
        int firstAdd = -1;
        for(int i = 0; i< list.size();i ++){

            int odd = 0;
            for(int j = 0;j < i;j ++){
                odd += map.get(list.get(j));
            }
            int first = map.get(list.get(i )) - odd;
            int second = n + 1 - tmp;
            int over;
            if((over = first * second) > 0){
                res += over;
                if(firstAdd == -1){
                    firstAdd = second;
                }
            }
            tmp --;
        }
        if(firstAdd >= 0){
            res -= firstAdd;
        }

        return res;


    }

    /*//再探插入排序
    public int leastInterval(char[] tasks, int n) {

        int time = 0;

        int done = 0;

        int all = 0;

        //当前剩余任务，先判断他，则保证先筛选出最多的任务，再进行是否是在冷却（适合冷却时间较少的算法）
        Map<Character,Integer> leftMap = new HashMap();

        //当前冷却时间信息 先判断他，则保证先筛选出不冷却的任务，再进行任务多少排序，稳定的两个循环（适合冷却时间较长的算法）
        Map<Character,Integer> cooldownMap = new HashMap();

        for(char c :tasks){

            leftMap.compute(c,(k,v) -> {

                if(v == null){
                    v = 1;
                }else{
                    v += 1;
                }
                return v;

            });

            cooldownMap.put(c,0);
            all ++;
        }

        while(done < all){

            Character max = null;
            int maxLeft = 0;
            Character min = null;
            int minCoolDown = 101;
            for(Map.Entry<Character,Integer> entry : cooldownMap.entrySet()){
                int tmpValue;
                if((tmpValue = entry.getValue()) == 0) {
                    int left = leftMap.get(entry.getKey());
                    if(left > maxLeft){
                        maxLeft = left;
                        max = entry.getKey();
                    }
                }else{
                    if(tmpValue < minCoolDown){
                        minCoolDown = tmpValue;
                        min = entry.getKey();
                    }
                }
            }
            if(max != null) {
                time ++;
                done ++;
                leftMap.put(max,leftMap.get(max) - 1);
                cooldownMap.put(max,n + 1);
                for(Map.Entry<Character,Integer> entry : cooldownMap.entrySet()){
                    if(entry.getValue() != 0) {
                        entry.setValue(entry.getValue() - 1);
                    }
                }
            }else{
                time += minCoolDown;
                for(Map.Entry<Character,Integer> entry : cooldownMap.entrySet()){
                    if(entry.getValue() != 0) {
                        entry.setValue(entry.getValue() - minCoolDown);
                    }
                }
            }


        }


       *//* while(done < all) {
            //回合大于一，先筛选出没冷却的，取剩余最多的任务
            if (n >= 1) {
                Character max = null;
                int maxLeft = 0;
                for(Map.Entry<Character,Integer> entry : cooldownMap.entrySet()){
                    if(entry.getValue() == 0) {
                        int left = leftMap.get(entry.getKey());
                        if(left > maxLeft){
                            maxLeft = left;
                            max = entry.getKey();
                        }
                    }
                }
                if(max != null) {
                    done ++;
                    leftMap.put(max,leftMap.get(max) - 1);
                    cooldownMap.put(max,n + 1);
                }
            }else{
                //回合小于等于1，先取出最多的任务，再判断有没有冷却
                Character max = null;
                int maxLeft = 0;

                while(max == null){
                    for(Map.Entry<Character,Integer> entry : leftMap.entrySet()){
                        int left = entry.getValue();
                        if(left > maxLeft){
                            maxLeft = left;
                            max = entry.getKey();
                        }
                    }
                    max = cooldownMap.get(max) > 0? null : max;

                }
                done ++;
                leftMap.put(max,leftMap.get(max) - 1);
                cooldownMap.put(max,n + 1);

            }

            time ++;
            for(Map.Entry<Character,Integer> entry : cooldownMap.entrySet()){
                if(entry.getValue() != 0) {
                    entry.setValue(entry.getValue() - 1);
                }
            }

        }*//*


        return time;

    }*/
}